{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Find Substring With Given Hash Value"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #string #sliding-window #hash-function #rolling-hash"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #字符串 #滑动窗口 #哈希函数 #滚动哈希"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: subStrHash"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #查找给定哈希值的子串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定整数 <code>p</code>&nbsp;和 <code>m</code>&nbsp;，一个长度为 <code>k</code>&nbsp;且下标从 <strong>0</strong>&nbsp;开始的字符串&nbsp;<code>s</code>&nbsp;的哈希值按照如下函数计算：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>hash(s, p, m) = (val(s[0]) * p<sup>0</sup> + val(s[1]) * p<sup>1</sup> + ... + val(s[k-1]) * p<sup>k-1</sup>) mod m</code>.</li>\n",
    "</ul>\n",
    "\n",
    "<p>其中&nbsp;<code>val(s[i])</code>&nbsp;表示&nbsp;<code>s[i]</code>&nbsp;在字母表中的下标，从&nbsp;<code>val('a') = 1</code> 到&nbsp;<code>val('z') = 26</code>&nbsp;。</p>\n",
    "\n",
    "<p>给你一个字符串&nbsp;<code>s</code>&nbsp;和整数&nbsp;<code>power</code>，<code>modulo</code>，<code>k</code>&nbsp;和&nbsp;<code>hashValue</code>&nbsp;。请你返回 <code>s</code>&nbsp;中 <strong>第一个</strong> 长度为 <code>k</code>&nbsp;的 <strong>子串</strong>&nbsp;<code>sub</code>&nbsp;，满足<em>&nbsp;</em><code>hash(sub, power, modulo) == hashValue</code>&nbsp;。</p>\n",
    "\n",
    "<p>测试数据保证一定 <strong>存在</strong>&nbsp;至少一个这样的子串。</p>\n",
    "\n",
    "<p><strong>子串</strong> 定义为一个字符串中连续非空字符组成的序列。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>s = \"leetcode\", power = 7, modulo = 20, k = 2, hashValue = 0\n",
    "<strong>输出：</strong>\"ee\"\n",
    "<strong>解释：</strong>\"ee\" 的哈希值为 hash(\"ee\", 7, 20) = (5 * 1 + 5 * 7) mod 20 = 40 mod 20 = 0 。\n",
    "\"ee\" 是长度为 2 的第一个哈希值为 0 的子串，所以我们返回 \"ee\" 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>s = \"fbxzaad\", power = 31, modulo = 100, k = 3, hashValue = 32\n",
    "<b>输出：</b>\"fbx\"\n",
    "<b>解释：</b>\"fbx\" 的哈希值为 hash(\"fbx\", 31, 100) = (6 * 1 + 2 * 31 + 24 * 31<sup>2</sup>) mod 100 = 23132 mod 100 = 32 。\n",
    "\"bxz\" 的哈希值为 hash(\"bxz\", 31, 100) = (2 * 1 + 24 * 31 + 26 * 31<sup>2</sup>) mod 100 = 25732 mod 100 = 32 。\n",
    "\"fbx\" 是长度为 3 的第一个哈希值为 32 的子串，所以我们返回 \"fbx\" 。\n",
    "注意，\"bxz\" 的哈希值也为 32 ，但是它在字符串中比 \"fbx\" 更晚出现。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= k &lt;= s.length &lt;= 2 * 10<sup>4</sup></code></li>\n",
    "\t<li><code>1 &lt;= power, modulo &lt;= 10<sup>9</sup></code></li>\n",
    "\t<li><code>0 &lt;= hashValue &lt; modulo</code></li>\n",
    "\t<li><code>s</code>&nbsp;只包含小写英文字母。</li>\n",
    "\t<li>测试数据保证一定 <strong>存在</strong>&nbsp;满足条件的子串。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [find-substring-with-given-hash-value](https://leetcode.cn/problems/find-substring-with-given-hash-value/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [find-substring-with-given-hash-value](https://leetcode.cn/problems/find-substring-with-given-hash-value/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"leetcode\"\\n7\\n20\\n2\\n0', '\"fbxzaad\"\\n31\\n100\\n3\\n32']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subStrHash(self, s: str, power: int, modulo: int, k: int, hashValue: int) -> str:\n",
    "        n = len(s)\n",
    "        p = 1\n",
    "        SUM = 0\n",
    "        ans = ''\n",
    "        for i in range(n - 1, n - 1 - k, -1):\n",
    "            SUM = (power * SUM + (ord(s[i]) - ord('a') + 1)) % modulo\n",
    "            p = p * power % modulo\n",
    "        if SUM == hashValue:\n",
    "            ans = i\n",
    "        i -= 1\n",
    "        while i >= 0:          \n",
    "            SUM = (power * SUM + (ord(s[i]) - ord('a') + 1) - p * (ord(s[i + k]) - ord('a') + 1)) % modulo\n",
    "            if SUM == hashValue:\n",
    "                ans = i\n",
    "            i -= 1\n",
    "        return s[ans:ans + k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subStrHash(self, s: str, power: int, modulo: int, k: int, hashValue: int) -> str:\n",
    "        mult = 1\n",
    "        n = len(s)\n",
    "        pos = -1\n",
    "        h = 0\n",
    "        for i in range(n - 1, n - k - 1, -1):\n",
    "            h = (h * power + (ord(s[i]) - ord('a') + 1)) % modulo\n",
    "            if i != n - k:\n",
    "                mult = mult * power % modulo\n",
    "        if h == hashValue:\n",
    "            pos = n - k\n",
    "        for i in range(n - k - 1, -1, -1):\n",
    "            h = ((h - (ord(s[i + k]) - ord('a') + 1) * mult % modulo + modulo) * power + \n",
    "            (ord(s[i]) - ord('a') + 1)) % modulo\n",
    "            if h == hashValue:\n",
    "                pos = i\n",
    "        return s[pos: pos + k]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subStrHash(self, s: str, power: int, modulo: int, k: int, hashValue: int) -> str:\n",
    "        # 滑动窗口\n",
    "        mult = 1\n",
    "        n = len(s)\n",
    "        pos = -1\n",
    "        h = 0\n",
    "        i = n - 1\n",
    "        while i >= n - k:\n",
    "            h = (h * power + (ord(s[i]) & 31)) % modulo\n",
    "            mult = mult * power % modulo\n",
    "            i -= 1\n",
    "        \n",
    "        if h == hashValue:\n",
    "            pos = n - k\n",
    "        \n",
    "        while i >= 0:\n",
    "            h = ((h * power - mult * (ord(s[i+k]) & 31) % modulo + modulo) + (ord(s[i]) & 31)) % modulo\n",
    "            if h == hashValue:\n",
    "                pos = i\n",
    "            i -= 1\n",
    "        \n",
    "        return s[pos : pos+k]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subStrHash(self, s: str, power: int, modulo: int, k: int, hashValue: int) -> str:\n",
    "        # 乘后取余和取余后乘再取余的结果是一样\n",
    "        t = pow(power, k - 1, modulo)\n",
    "        val = ans = 0\n",
    "        # 正向计算出前k个的值\n",
    "        for i in range(k):\n",
    "            val = (val + (ord(s[len(s) - 1 -i]) - ord('a') + 1) * pow(power, k - 1 - i, modulo) % modulo) % modulo\n",
    "        if val == hashValue:\n",
    "            ans = len(s) - k\n",
    "        # 逆序移动滑动窗口窗口\n",
    "        for i in range(len(s) - 1, k - 1, -1):\n",
    "            val = (val - (ord(s[i]) - ord('a') + 1) * t % modulo) % modulo\n",
    "            val = val * power  % modulo\n",
    "            val = (val + ord(s[i - k]) - ord('a') + 1) % modulo \n",
    "            if val == hashValue:\n",
    "                ans = i - k\n",
    "        return s[ans:ans+k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def subStrHash(self, s: str, power: int, modulo: int, k: int, hashValue: int) -> str:\r\n",
    "        hs = 0\r\n",
    "        n = len(s)\r\n",
    "        res = -1\r\n",
    "        for i in range(n - 1, -1, -1):\r\n",
    "            if i < n - k:\r\n",
    "                hs = (modulo + hs - (ord(s[i + k]) - 96) * pow(power, k - 1, modulo) % modulo) % modulo\r\n",
    "            hs = ((hs * power) % modulo + ord(s[i]) - 96) % modulo\r\n",
    "            if i <= n - k and hs == hashValue:\r\n",
    "                res = i\r\n",
    "        \r\n",
    "        return s[res:res+k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subStrHash(self, s: str, power: int, modulo: int, k: int, hashValue: int) -> str:\n",
    "        mp = range(1, 27)\n",
    "        # 除法不能保证mod的正确性\n",
    "        n = len(s)\n",
    "        ans, val, mul = n, 0, 1\n",
    "        for i in range(n - 1, n - k - 1, -1):\n",
    "            val = (val * power + mp[ord(s[i]) - ord('a')]) % modulo\n",
    "            mul = (mul * power) % modulo\n",
    "        if val == hashValue:\n",
    "            ans = n - k\n",
    "        # 减去一个k次方\n",
    "        for i in range(n - k - 1, -1, -1):\n",
    "            val = (val * power - mp[ord(s[i + k]) - ord('a')] * mul % modulo + mp[ord(s[i]) - ord('a')] + modulo) % modulo\n",
    "            if val == hashValue:\n",
    "                ans = i\n",
    "        return s[ans: ans + k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subStrHash(self, s: str, power: int, modulo: int, k: int, hashValue: int) -> str:\n",
    "        t = pow(power, k - 1, modulo)\n",
    "        val = ans = 0\n",
    "        for i in range(k):\n",
    "            val = (val + (ord(s[len(s) - 1 -i]) - ord('a') + 1) * pow(power, k - 1 - i, modulo) % modulo) % modulo\n",
    "        if val == hashValue:\n",
    "            ans = len(s) - k\n",
    "        for i in range(len(s) - 1, k - 1, -1):\n",
    "            val = (val - (ord(s[i]) - ord('a') + 1) * t % modulo) % modulo\n",
    "            val = val * power  % modulo\n",
    "            val = (val + ord(s[i - k]) - ord('a') + 1) % modulo \n",
    "            if val == hashValue:\n",
    "                ans = i - k\n",
    "        return s[ans:ans+k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subStrHash(self, s: str, power: int, modulo: int, k: int, hashValue: int) -> str:\n",
    "        #整体思路从后往前迭代,这样避免除法,乘法可以维护取模的恒等性。\n",
    "        t = pow(power, k - 1, modulo)\n",
    "        val = ans = 0\n",
    "        #从后往前初始化答案子串\n",
    "        for i in range(k):\n",
    "            val = (val + (ord(s[len(s) - 1 -i]) - ord('a') + 1) * pow(power, k - 1 - i, modulo) % modulo) % modulo\n",
    "        #题意返回正着数第一个,那就是倒着数最后一个\n",
    "        if val == hashValue:\n",
    "            ans = len(s) - k\n",
    "        #倒着的滑动窗口\n",
    "        for i in range(len(s) - 1, k - 1, -1):\n",
    "            #右端点左移，减去\n",
    "            val = (val - (ord(s[i]) - ord('a') + 1) * t % modulo) % modulo\n",
    "            val = val * power  % modulo\n",
    "            #左端点左移，加上\n",
    "            val = (val + ord(s[i - k]) - ord('a') + 1) % modulo \n",
    "            if val == hashValue:\n",
    "                ans = i - k\n",
    "        return s[ans:ans+k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "sys.set_int_max_str_digits(1000000000)\n",
    "def v(c):\n",
    "    return ord(c)-ord('a')+1\n",
    "\n",
    "class Solution:\n",
    "    def subStrHash(self, s: str, power: int, md: int, k: int, hV: int) -> str:\n",
    "        temp = 0\n",
    "        n = len(s)\n",
    "        res = -1\n",
    "        for i in range(n-k,n):\n",
    "            temp += pow(power,i-n+k,md) * v(s[i])\n",
    "            temp %= md\n",
    "        if temp == hV:res = n-k\n",
    "        \n",
    "        for epos in range(n-k-1,-1,-1):\n",
    "            temp -= pow(power,k-1,md)*v(s[epos+k])\n",
    "            temp %= md\n",
    "            temp *= power\n",
    "            temp += v(s[epos])\n",
    "            temp %= md\n",
    "            if temp == hV:res = epos\n",
    "        return s[res:res+k]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subStrHash(self, s: str, power: int, modulo: int, k: int, hashValue: int) -> str:\n",
    "        mult = pow(power, k - 1, modulo)   # power^(k-1) mod modulo\n",
    "        n = len(s)\n",
    "        pos = -1   # first position\n",
    "        h = 0   # hash val\n",
    "        for i in range(n - 1, n - k - 1, -1):\n",
    "            h = (h * power + (ord(s[i]) - ord('a') + 1)) % modulo\n",
    "        if h == hashValue:\n",
    "            pos = n - k\n",
    "        # from backward\n",
    "        for i in range(n - k - 1, -1, -1):\n",
    "            h = ((h - (ord(s[i+k]) - ord('a') + 1) * mult % modulo) * power) % modulo # python no need to plus modulo\n",
    "            h = (h + (ord(s[i]) - ord('a') + 1)) % modulo\n",
    "            if h == hashValue:\n",
    "                pos = i\n",
    "        return s[pos:pos+k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subStrHash(self, s: str, power: int, modulo: int, k: int, hashValue: int) -> str:\n",
    "        # 滑动窗口\n",
    "        mult = 1\n",
    "        n = len(s)\n",
    "        pos = -1\n",
    "        h = 0\n",
    "        i = n - 1\n",
    "        while i >= n - k:\n",
    "            h = (h * power + (ord(s[i]) & 31)) % modulo\n",
    "            mult = mult * power % modulo\n",
    "            i -= 1\n",
    "        \n",
    "        if h == hashValue:\n",
    "            pos = n - k\n",
    "        \n",
    "        while i >= 0:\n",
    "            # 计算新 hash 值时多加一个 modulo 避免负数值不匹配问题\n",
    "            h = ((ord(s[i]) & 31) + h * power % modulo - mult * (ord(s[i+k]) & 31) % modulo + modulo) % modulo\n",
    "            if h == hashValue:\n",
    "                pos = i\n",
    "            i -= 1\n",
    "        \n",
    "        return s[pos : pos+k]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subStrHash(self, s: str, power: int, modulo: int, k: int, hashValue: int) -> str:\n",
    "        mult = 1   # power^k mod modulo\n",
    "        n = len(s)\n",
    "        pos = -1   # 第一个符合要求子串的起始下标\n",
    "        h = 0   # 子串哈希值\n",
    "        for i in range(n-1,n-k-1,-1):\n",
    "            h=(h*power+(ord(s[i])-ord('a')+1))%modulo\n",
    "            if i!=n-k:\n",
    "                mult = mult * power %modulo\n",
    "        if h==hashValue:\n",
    "            pos=n-k\n",
    "        for i in range(n-k-1,-1,-1):\n",
    "            h = ((h-(ord(s[i+k])-ord('a')+1)*mult%modulo+modulo)*power+(ord(s[i])-ord('a')+1))%modulo\n",
    "            if h == hashValue:\n",
    "                pos = i\n",
    "        return s[pos:pos+k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subStrHash(self, s: str, power: int, modulo: int, k: int, hashValue: int) -> str:\n",
    "        mult = 1   # power^k mod modulo\n",
    "        n = len(s)\n",
    "        pos = -1   # 第一个符合要求子串的起始下标\n",
    "        h = 0   # 子串哈希值\n",
    "        # 预处理计算最后一个子串的哈希值和 power^k mod modulo\n",
    "        for i in range(n - 1, n - k - 1, -1):\n",
    "            h = (h * power + (ord(s[i]) - ord('a') + 1)) % modulo\n",
    "            if i != n - k:\n",
    "                mult = mult * power % modulo\n",
    "        if h == hashValue:\n",
    "            pos = n - k\n",
    "        # 向前计算哈希值并尝试更新下标\n",
    "        for i in range(n - k - 1, -1, -1):\n",
    "            h = ((h - (ord(s[i+k]) - ord('a') + 1) * mult % modulo + modulo) * power + (ord(s[i]) - ord('a') + 1)) % modulo\n",
    "            if h == hashValue:\n",
    "                pos = i\n",
    "        return s[pos:pos+k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subStrHash(self, s: str, power: int, modulo: int, k: int, hashValue: int) -> str:\n",
    "        t=pow(power,k-1,modulo)\n",
    "        val=0\n",
    "        n=len(s)\n",
    "        for i in range(n-1,n-k,-1):\n",
    "            val=(val+pow(power,k-n+i,modulo)*(ord(s[i])-ord('a')+1)%modulo)\n",
    "        ans=0\n",
    "        for i in range(n-k,-1,-1):\n",
    "            val=(val+(ord(s[i])-ord('a')+1))%modulo\n",
    "            if val==hashValue:\n",
    "                ans=i\n",
    "            val-=t*(ord(s[i+k-1])-ord('a')+1)\n",
    "            val=val*power%modulo\n",
    "\n",
    "        return s[ans:ans+k]\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subStrHash(self, s: str, power: int, modulo: int, k: int, hashValue: int) -> str:\n",
    "        # hash_t = 0\n",
    "        # magin = ord('a') - 1\n",
    "        # n = len(s)\n",
    "\n",
    "        # for i in range(n - 1, n - k - 1, -1):\n",
    "        #     hash_t = (hash_t * power + ord(s[i]) - magin) % modulo\n",
    "\n",
    "        # product = pow(power, k - 1) % modulo\n",
    "        # for i in range(n - k - 1, -1, -1):\n",
    "        #     if hash_t == hashValue:\n",
    "        #         return s[i+1 : i+k+1]\n",
    "        #     hash_t = (hash_t - (ord(s[i + k]) - magin) * product) % modulo\n",
    "        #     hash_t = (hash_t * power + ord(s[i]) - magin) % modulo\n",
    "        #     hash_t = (hash_t + modulo) % modulo\n",
    "\n",
    "        mult = 1   # power^k mod modulo\n",
    "        n = len(s)\n",
    "        pos = -1   # 第一个符合要求子串的起始下标\n",
    "        h = 0   # 子串哈希值\n",
    "        # 预处理计算最后一个子串的哈希值和 power^k mod modulo\n",
    "        for i in range(n - 1, n - k - 1, -1):\n",
    "            h = (h * power + (ord(s[i]) - ord('a') + 1)) % modulo\n",
    "            if i != n - k:\n",
    "                mult = mult * power % modulo\n",
    "        if h == hashValue:\n",
    "            pos = n - k\n",
    "        # 向前计算哈希值并尝试更新下标\n",
    "        for i in range(n - k - 1, -1, -1):\n",
    "            h = ((h - (ord(s[i+k]) - ord('a') + 1) * mult % modulo + modulo) * power + (ord(s[i]) - ord('a') + 1)) % modulo\n",
    "            if h == hashValue:\n",
    "                pos = i\n",
    "        return s[pos:pos+k]\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def get_val(s:str) -> int:\n",
    "    return ord(s[0])-96\n",
    "class Solution:\n",
    "    def subStrHash(self, s: str, power: int, modulo: int, k: int, hashValue: int) -> str:\n",
    "        n=len(s)\n",
    "        p=[i for i in range(k)]\n",
    "        cur = 1\n",
    "        for i in range(k):\n",
    "            p[i] = cur\n",
    "            cur = cur * power % modulo\n",
    "        curHash=0\n",
    "        ans=0\n",
    "        for i in range(n-1,n-k-1,-1):\n",
    "            curHash=(curHash+get_val(s[i])*p[k+i-n])%modulo\n",
    "        if curHash==hashValue:\n",
    "            ans=n-k\n",
    "        for i in range(n-k-1,-1,-1):\n",
    "            curHash=((curHash-get_val(s[i+k])*p[k-1])*power+get_val(s[i]))%modulo\n",
    "            if curHash == hashValue:\n",
    "                ans=i\n",
    "        return s[ans:ans+k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subStrHash(self, s: str, power: int, modulo: int, k: int, hashValue: int) -> str:\n",
    "        n = len(s)\n",
    "        p = 1\n",
    "        SUM = 0\n",
    "        ans = ''\n",
    "        for i in range(n - 1, n - 1 - k, -1):\n",
    "            SUM = (power * SUM + (ord(s[i]) - ord('a') + 1)) % modulo\n",
    "            p = p * power % modulo\n",
    "        if SUM == hashValue:\n",
    "            ans = s[i:]\n",
    "        #print(p)\n",
    "        i -= 1\n",
    "        while i >= 0:\n",
    "            \n",
    "            SUM = (power * SUM + (ord(s[i]) - ord('a') + 1) - p * (ord(s[i + k]) - ord('a') + 1)) % modulo\n",
    "            #print(i, i + k, n, p, SUM)\n",
    "            if SUM == hashValue:\n",
    "                ans = s[i: i + k]\n",
    "            i -= 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subStrHash(self, s: str, power: int, modulo: int, k: int, hashValue: int) -> str:\n",
    "        # 滑动窗口\n",
    "        mult = 1\n",
    "        n = len(s)\n",
    "        pos = -1\n",
    "        h = 0\n",
    "        i = n - 1\n",
    "        while i >= n - k:\n",
    "            h = (h * power + (ord(s[i]) & 31)) % modulo\n",
    "            mult = mult * power % modulo\n",
    "            i -= 1\n",
    "        \n",
    "        if h == hashValue:\n",
    "            pos = n - k\n",
    "        \n",
    "        while i >= 0:\n",
    "            # 计算新 hash 值时多加一个 modulo 避免负数值不匹配问题\n",
    "            h = ((ord(s[i]) & 31) + h * power - mult * (ord(s[i+k]) & 31) + modulo) % modulo\n",
    "            if h == hashValue:\n",
    "                pos = i\n",
    "            i -= 1\n",
    "        \n",
    "        return s[pos : pos+k]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subStrHash(self, s: str, power: int, modulo: int, k: int, hashValue: int) -> str:\n",
    "        #整体思路从后往前迭代,这样避免除法,维护取模的恒等性。\n",
    "        t = pow(power, k - 1, modulo)\n",
    "        val = ans = 0\n",
    "        #从后往前初始化答案子串\n",
    "        for i in range(k):\n",
    "            val = (val + (ord(s[len(s) - 1 -i]) - ord('a') + 1) * pow(power, k - 1 - i, modulo) % modulo) % modulo\n",
    "        if val == hashValue:\n",
    "            ans = len(s) - k\n",
    "        for i in range(len(s) - 1, k - 1, -1):\n",
    "            val = (val - (ord(s[i]) - ord('a') + 1) * t % modulo) % modulo\n",
    "            val = val * power  % modulo\n",
    "            val = (val + ord(s[i - k]) - ord('a') + 1) % modulo \n",
    "            if val == hashValue:\n",
    "                ans = i - k\n",
    "        return s[ans:ans+k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subStrHash(self, s: str, power: int, modulo: int, k: int, hashValue: int) -> str:\n",
    "        t = pow(power, k - 1, modulo)\n",
    "        val = ans = 0\n",
    "        for i in range(k):\n",
    "            val = (val + (ord(s[len(s) - 1 -i]) - ord('a') + 1) * pow(power, k - 1 - i, modulo) % modulo) % modulo\n",
    "        if val == hashValue:\n",
    "            ans = len(s) - k\n",
    "        for i in range(len(s) - 1, k - 1, -1):\n",
    "            val = (val - (ord(s[i]) - ord('a') + 1) * t % modulo) % modulo\n",
    "            val = val * power  % modulo\n",
    "            val = (val + ord(s[i - k]) - ord('a') + 1) % modulo \n",
    "            if val == hashValue:\n",
    "                ans = i - k\n",
    "        return s[ans:ans+k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subStrHash(self, s: str, power: int, modulo: int, k: int, hashValue: int) -> str:\n",
    "        p, m = power, modulo\n",
    "        n = len(s)\n",
    "        mult = 1\n",
    "        t = 0\n",
    "        for i in range(n-1,n-k-1,-1):\n",
    "            v = ord(s[i]) - ord('a') + 1\n",
    "            t = (t * p + v) % m\n",
    "            if i != n - k:\n",
    "                mult = mult * p % m\n",
    "        pos = -1\n",
    "        if t == hashValue: \n",
    "            pos = n - k\n",
    "        for i in range(n-k-1, -1, -1):\n",
    "            v_l = ord(s[i]) - ord('a') + 1\n",
    "            v_r = ord(s[i + k]) - ord('a') + 1\n",
    "            t = (t - (v_r * mult) % m + m) % m\n",
    "            t = ((t * p) % m + v_l + m) % m\n",
    "            if t == hashValue:\n",
    "                pos = i\n",
    "        return s[pos:pos+k] \n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subStrHash(self, s: str, power: int, modulo: int, k: int, hashValue: int) -> str:\n",
    "        p, m = power, modulo\n",
    "        n = len(s)\n",
    "        mult = 1\n",
    "        t = 0\n",
    "        for i in range(n-1,n-k-1,-1):\n",
    "            v = ord(s[i]) - ord('a') + 1\n",
    "            t = (t * p + v) % m\n",
    "        pos = -1\n",
    "        if t == hashValue: \n",
    "            pos = n - k\n",
    "        for i in range(n-k-1, -1, -1):\n",
    "            v_l = ord(s[i]) - ord('a') + 1\n",
    "            v_r = ord(s[i + k]) - ord('a') + 1\n",
    "            t = (t - v_r * pow(p, k - 1, m) + m) % m\n",
    "            t = ((t * p) % m + v_l + m) % m\n",
    "            if t == hashValue:\n",
    "                pos = i\n",
    "        return s[pos:pos+k] \n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subStrHash(self, s: str, power: int, modulo: int, k: int, hashValue: int) -> str:\n",
    "        p, m = power, modulo\n",
    "        n = len(s)\n",
    "        t = 0\n",
    "        for i in range(n-1,n-k-1,-1):\n",
    "            v = ord(s[i]) - ord('a') + 1\n",
    "            j = k - (n - i)\n",
    "            t = (t + v * pow(p, j, m)) % m\n",
    "        pos = -1\n",
    "        if t == hashValue: \n",
    "            pos = n - k\n",
    "        for i in range(n-k-1, -1, -1):\n",
    "            v_l = ord(s[i]) - ord('a') + 1\n",
    "            v_r = ord(s[i + k]) - ord('a') + 1\n",
    "            t = (t - v_r * pow(p, k - 1, m) + m) % m\n",
    "            t = ((t * p) % m + v_l + m) % m\n",
    "            if t == hashValue:\n",
    "                pos = i\n",
    "        return s[pos:pos+k] \n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subStrHash(self, s: str, power: int, modulo: int, k: int, hashValue: int) -> str:\n",
    "        hash_t = 0\n",
    "        magin = ord('a') - 1\n",
    "        n = len(s)\n",
    "        pos = -1\n",
    "\n",
    "        for i in range(n - 1, n - k - 1, -1):\n",
    "            hash_t = (hash_t * power + ord(s[i]) - magin) % modulo\n",
    "        if hash_t == hashValue:\n",
    "            pos = n - k\n",
    "        product = pow(power, k - 1) % modulo\n",
    "        for i in range(n - k - 1, -1, -1):\n",
    "            hash_t = (hash_t - (ord(s[i + k]) - magin) * product) % modulo\n",
    "            hash_t = (hash_t * power + ord(s[i]) - magin) % modulo\n",
    "            hash_t = (hash_t + modulo) % modulo\n",
    "            if hash_t == hashValue:\n",
    "                pos = i\n",
    "\n",
    "        return s[pos:pos+k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subStrHash(self, s: str, power: int, modulo: int, k: int, hashValue: int) -> str:\n",
    "        mult = 1   # power^k mod modulo\n",
    "        n = len(s)\n",
    "        pos = -1   # 第一个符合要求子串的起始下标\n",
    "        h = 0   # 子串哈希值\n",
    "        # 预处理计算最后一个子串的哈希值和 power^k mod modulo\n",
    "        for i in range(n - 1, n - k - 1, -1):\n",
    "            h = (h * power + (ord(s[i]) - ord('a') + 1)) % modulo\n",
    "            if i != n - k:\n",
    "                mult = mult * power % modulo\n",
    "        if h == hashValue:\n",
    "            pos = n - k\n",
    "        # 向前计算哈希值并尝试更新下标\n",
    "        for i in range(n - k - 1, -1, -1):\n",
    "            h = ((h - (ord(s[i+k]) - ord('a') + 1) * mult % modulo + modulo) * power + (ord(s[i]) - ord('a') + 1)) % modulo\n",
    "            if h == hashValue:\n",
    "                pos = i\n",
    "        return s[pos:pos+k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import *\n",
    "from math import *\n",
    "from functools import cache\n",
    "from queue import *\n",
    "from heapq import *\n",
    "from bisect import bisect_left\n",
    "# start-----------------------------------------------------\n",
    "class Solution:\n",
    "    def subStrHash(self, s: str, power: int, modulo: int, k: int, hashValue: int) -> str:\n",
    "        n = len(s)\n",
    "        pos = n - 1\n",
    "        h = 0\n",
    "        ans = -1\n",
    "        pk = 1\n",
    "        a = k\n",
    "        while k:\n",
    "            h = (h * power + ord(s[pos]) - 96) % modulo\n",
    "            pos -= 1\n",
    "            k -= 1\n",
    "            if k:\n",
    "                pk = pk * power % modulo\n",
    "        if h == hashValue:\n",
    "            ans = pos + 1\n",
    "        k = a\n",
    "        while pos >= 0:\n",
    "            h = (h - (ord(s[pos + k]) - 96) * pk) % modulo\n",
    "            h = (h  * power + ord(s[pos]) - 96) % modulo\n",
    "            if h == hashValue:\n",
    "                ans = pos\n",
    "            pos -= 1\n",
    "        return s[ans:ans+k]\n",
    "s = Solution()\n",
    "s.subStrHash('leetcode',7,20,2,0)\n",
    "# end-------------------------------------------------------"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subStrHash(self, s: str, power: int, modulo: int, k: int, hashValue: int) -> str:\n",
    "        hash_t = 0\n",
    "        magin = ord('a') - 1\n",
    "        n = len(s)\n",
    "        pos = -1\n",
    "\n",
    "        for i in range(n - 1, n - k - 1, -1):\n",
    "            hash_t = (hash_t * power + ord(s[i]) - magin) % modulo\n",
    "        if hash_t == hashValue:\n",
    "            pos = n - k\n",
    "        product = pow(power, k - 1) % modulo\n",
    "        for i in range(n - k - 1, -1, -1):\n",
    "            hash_t = (hash_t - (ord(s[i + k]) - magin) * product) % modulo\n",
    "            hash_t = (hash_t * power + ord(s[i]) - magin) % modulo\n",
    "            hash_t = (hash_t + modulo) % modulo\n",
    "            if hash_t == hashValue:\n",
    "                pos = i\n",
    "\n",
    "        return s[pos:pos+k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subStrHash(self, s: str, power: int, modulo: int, k: int, hashValue: int) -> str:\n",
    "        h = 0\n",
    "        L = len(s)\n",
    "        ordA = ord('a') - 1\n",
    "        if power % modulo == 0:\n",
    "            for i, c in enumerate(s[:L-k+1]):\n",
    "                h = ord(c) - ordA\n",
    "                if h % modulo == hashValue:\n",
    "                    return s[i:i+k]\n",
    "        off = -1\n",
    "        pk = (power**k) % modulo\n",
    "        for i, c in enumerate(reversed(s)):\n",
    "            h = h*power + ord(c) - ordA\n",
    "            if i >= k:\n",
    "                h -= (ord(s[L-1-i+k]) - ordA) * pk\n",
    "            h %= modulo\n",
    "            if h == hashValue:\n",
    "                off = i\n",
    "        return s[L-1-off:L-1-off+k]\n",
    "        #h = 0\n",
    "        #ordA = ord('a') - 1\n",
    "        #pk = (power**(k-1)) % modulo\n",
    "        #for i, c in enumerate(s):\n",
    "        #    h = ((h - ord(s[i-k]) + ordA) if i >= k else h) // power + (ord(c)-ordA)*pk\n",
    "        #    if i >= k - 1 and h % modulo == hashValue:\n",
    "        #        return s[i-k+1:i+1]\n",
    "        # (x - v0)/p+vk*p**(k-1)\n",
    "\n",
    "        # y * (x*mod+z) % mod = y*z\n",
    "\n",
    "        # v * (p**k) = v*(p**(k-1)*p) = v*(p**(k-1))\n",
    "        # hn*mod+rn \n",
    "        # (hn*mod+rn - v0) = pn*p  /p - v[k]*p**k + v[0]\n",
    "        # rn*p - v[k]*pk + v[0]\n",
    "        # rn % mod - v0 %mod = (pn*mod+pr)*(pr1 % mod\n",
    "        # "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subStrHash(self, s: str, power: int, modulo: int, k: int, hashValue: int) -> str:\n",
    "\n",
    "        n = len(s)\n",
    "        s = s[::-1]\n",
    "        hash_s = 0\n",
    "\n",
    "        for i in range(k):\n",
    "            hash_s = hash_s * power + (ord(s[i])-96)\n",
    "    \n",
    "        p = pow(power, k- 1)\n",
    "    \n",
    "        for i in range(n - k + 1):\n",
    "            if hash_s % modulo == hashValue:\n",
    "                s0 = s[i:i+k]\n",
    "                \n",
    "            if i < n - k: \n",
    "                hash_s = hash_s - p * (ord(s[i])-96) \n",
    "                hash_s = hash_s * power + (ord(s[i+k])-96) \n",
    "\n",
    "        return s0[::-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subStrHash(self, s: str, power: int, modulo: int, k: int, hashValue: int) -> str:\n",
    "        hash_t = 0\n",
    "        magin = ord('a') - 1\n",
    "        n = len(s)\n",
    "        pos = -1\n",
    "\n",
    "        for i in range(n - 1, n - k - 1, -1):\n",
    "            hash_t = (hash_t * power + ord(s[i]) - magin) % modulo\n",
    "        if hash_t == hashValue:\n",
    "            pos = n - k\n",
    "        product = pow(power, k - 1) % modulo\n",
    "        for i in range(n - k - 1, -1, -1):\n",
    "            hash_t = (hash_t - (ord(s[i + k]) - magin) * product) % modulo\n",
    "            hash_t = (hash_t * power + ord(s[i]) - magin) % modulo\n",
    "            hash_t = (hash_t + modulo) % modulo\n",
    "            if hash_t == hashValue:\n",
    "                pos = i\n",
    "\n",
    "        return s[pos:pos+k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subStrHash(self, s: str, power: int, modulo: int, k: int, hashValue: int) -> str:\n",
    "        hash_t = 0\n",
    "        magin = ord('a') - 1\n",
    "        n = len(s)\n",
    "        pos = -1\n",
    "\n",
    "        for i in range(n - 1, n - k - 1, -1):\n",
    "            hash_t = (hash_t * power + ord(s[i]) - magin) % modulo\n",
    "        if hash_t == hashValue:\n",
    "            pos = n - k\n",
    "        product = pow(power, k - 1) % modulo\n",
    "        for i in range(n - k - 1, -1, -1):\n",
    "            hash_t = (hash_t - (ord(s[i + k]) - magin) * product) % modulo\n",
    "            hash_t = (hash_t * power + ord(s[i]) - magin) % modulo\n",
    "            hash_t = (hash_t + modulo) % modulo\n",
    "            if hash_t == hashValue:\n",
    "                pos = i\n",
    "\n",
    "        return s[pos:pos+k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def subStrHash(self, s: str, power: int, modulo: int, k: int, hashValue: int) -> str:\n",
    "        sn = [ord(c) - ord('a') + 1 for c in s]\n",
    "        ans_idx = -1\n",
    "        val = 0\n",
    "        n = len(sn)\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            val = (val * power + sn[i]) % modulo\n",
    "            if i <= n - 1 - k:\n",
    "                val = (val - sn[i + k] * pow(power, k, modulo)) % modulo\n",
    "            if i <= n - k and val == hashValue:\n",
    "                ans_idx = i\n",
    "        return s[ans_idx:ans_idx + k]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subStrHash(self, s: str, power: int, modulo: int, k: int, hashValue: int) -> str:\n",
    "        nums = [(ord(x) - ord('a') + 1) for x in s]\n",
    "        n = len(nums)\n",
    "        i, cnt, ans = n - 1, 0, n - 1\n",
    "        # 由于正向减去再除去不一定得到的是整数，会有误差\n",
    "        # 反向乘法会好些\n",
    "        m = power ** (k - 1)% modulo\n",
    "        for j in range(n - 1, -1, -1):\n",
    "            if i - j + 1 > k:\n",
    "                cnt = (cnt - (nums[i] * m % modulo) % modulo + modulo)%modulo\n",
    "                i -= 1\n",
    "            cnt = ((cnt * power) % modulo + nums[j] % modulo) % modulo\n",
    "            if i - j + 1 == k and cnt == hashValue:\n",
    "                ans = j\n",
    "        return s[ans:ans + k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subStrHash(self, s: str, power: int, modulo: int, k: int, hashValue: int) -> str:\n",
    "        nums = [(ord(x) - ord('a') + 1) for x in s]\n",
    "        n = len(nums)\n",
    "        i, cnt, ans = n - 1, 0, n - 1\n",
    "        # 由于正向减去再除去不一定得到的是整数，会有误差\n",
    "        # 反向乘法会好些\n",
    "        \"\"\"\n",
    "        m = power ** (k - 1)% modulo 这一句拿出来算，我在里面算，超时了好多次\\U0001f972\n",
    "        \"\"\"\n",
    "        m = power ** (k - 1)% modulo\n",
    "        for j in range(n - 1, -1, -1):\n",
    "            if i - j + 1 > k:\n",
    "                cnt = (cnt - (nums[i] * m) % modulo)\n",
    "                i -= 1\n",
    "            cnt = ((cnt * power) % modulo + nums[j] % modulo) % modulo\n",
    "            if i - j + 1 == k and cnt == hashValue:\n",
    "                ans = j\n",
    "        return s[ans:ans + k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subStrHash(self, s: str, power: int, modulo: int, k: int, hashValue: int) -> str:\n",
    "\n",
    "        hs, n, s, p = 0, len(s), s[::-1], pow(power, k-1)\n",
    "\n",
    "        for i in range(k):\n",
    "            hs = hs * power + (ord(s[i])-96)\n",
    "    \n",
    "        for i in range(n - k + 1):\n",
    "            if hs % modulo == hashValue:\n",
    "                s0 = s[i:i+k]\n",
    "                \n",
    "            if i < n - k: \n",
    "                hs -= p * (ord(s[i])-96) \n",
    "                hs = hs * power + (ord(s[i+k])-96) \n",
    "\n",
    "        return s0[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subStrHash(self, s: str, power: int, modulo: int, k: int, hashValue: int) -> str:\n",
    "        nums = [ord(x) - ord('a') + 1 for x in s]\n",
    "        tot = 0\n",
    "        n = len(s)\n",
    "        def quickpower(k, p):\n",
    "            double = power\n",
    "            while p:\n",
    "                if p & 1:\n",
    "                    k = k * double % modulo\n",
    "                double = double * double % modulo\n",
    "                p >>= 1\n",
    "            return k\n",
    "        \n",
    "        for i in range(n - k, n):\n",
    "            last = quickpower(nums[i], i - (n - k)) \n",
    "            tot = (tot + last) % modulo\n",
    "        if tot == hashValue:\n",
    "            ret = n - k\n",
    "        for i in range(n - k - 1, -1, -1):\n",
    "            tot = ((tot - last) * power + nums[i]) % modulo\n",
    "            if tot == hashValue:\n",
    "                ret = i\n",
    "            # print(s[i:i + k], tot)\n",
    "            last = quickpower(nums[i + k - 1], k - 1)\n",
    "        return s[ret: ret + k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subStrHash(self, s: str, power: int, modulo: int, k: int, hashValue: int) -> str:\n",
    "        nums = [(ord(x) - ord('a') + 1) for x in s]\n",
    "        n = len(nums)\n",
    "        i, cnt, ans = n - 1, 0, n - 1\n",
    "        # 由于正向减去再除去不一定得到的是整数，会有误差\n",
    "        # 反向乘法会好些\n",
    "        \"\"\"\n",
    "        m = power ** (k - 1)% modulo 这一句拿出来算，我在里面算，超时了好多次\\U0001f972\n",
    "        \"\"\"\n",
    "        m = power ** (k - 1)% modulo\n",
    "        for j in range(n - 1, -1, -1):\n",
    "            if i - j + 1 > k:\n",
    "                cnt = (cnt - (nums[i] * m) % modulo)\n",
    "                i -= 1\n",
    "            cnt = ((cnt * power) % modulo + nums[j] % modulo) % modulo\n",
    "            if i - j + 1 == k and cnt == hashValue:\n",
    "                ans = j\n",
    "        return s[ans:ans + k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subStrHash(self, s: str, power: int, modulo: int, k: int, hashValue: int) -> str:\n",
    "        nums = [(ord(x) - ord('a') + 1) for x in s]\n",
    "        n = len(nums)\n",
    "        i, cnt, ans = n - 1, 0, n - 1\n",
    "        # 由于正向减去再除去不一定得到的是整数，会有误差\n",
    "        # 反向乘法会好些\n",
    "        \"\"\"\n",
    "        m = power ** (k - 1)% modulo 这一句拿出来算，我在里面算，超时了好多次\\U0001f972\n",
    "        \"\"\"\n",
    "        m = power ** (k - 1)% modulo\n",
    "        for j in range(n - 1, -1, -1):\n",
    "            if i - j + 1 > k:\n",
    "                cnt = (cnt - (nums[i] * m) % modulo)\n",
    "                i -= 1\n",
    "            cnt = ((cnt * power) % modulo + nums[j] % modulo) % modulo\n",
    "            if i - j + 1 == k and cnt == hashValue:\n",
    "                ans = j\n",
    "        return s[ans:ans + k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subStrHash(self, s: str, p: int, mod: int, k: int, hashValue: int) -> str:\n",
    "        def val(ch):\n",
    "            return ord(ch)-ord('a')+1\n",
    "        value=0\n",
    "        n=len(s)\n",
    "        for i in range(k):\n",
    "            value=value*p+val(s[n-1-i])\n",
    "        value%=mod\n",
    "        mul=pow(p,k-1)\n",
    "        last=-1\n",
    "        if value==hashValue:\n",
    "            last=n-k\n",
    "            #return s[n-k:]\n",
    "        for i in range(k,n):\n",
    "            print(i)\n",
    "            print(s[n+k-i-1],s[n-1-i])\n",
    "            value-=val(s[n+k-i-1])*mul\n",
    "            value=value*p+val(s[n-1-i])\n",
    "            value%=mod\n",
    "            if value==hashValue:\n",
    "                last=n-i-1\n",
    "                #return s[n-i-1:n-i+k-1]\n",
    "        return s[last:last+k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subStrHash(self, s: str, power: int, modulo: int, k: int, hashValue: int) -> str:\n",
    "\n",
    "        hs, n, p = 0, len(s), pow(power, k-1)\n",
    "\n",
    "        for i in range(k-1,-1,-1):\n",
    "            hs = hs * power + (ord(s[i])-96) % modulo\n",
    "    \n",
    "        for i in range(n - k + 1):\n",
    "            if hs % modulo == hashValue:\n",
    "                return s[i:i+k]\n",
    "                \n",
    "            if i < n - k: \n",
    "                hs -= (ord(s[i])-96) % modulo\n",
    "                hs = (hs // power + (ord(s[i+k])-96)*p)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subStrHash(self, s: str, power: int, modulo: int, k: int, hashValue: int) -> str:\n",
    "        d = {'a': 1, 'b': 2, 'c': 3, 'd': 4, 'e': 5, 'f': 6, 'g': 7, 'h': 8, \n",
    "        'i': 9, 'j': 10, 'k': 11, 'l': 12, 'm': 13, 'n': 14, 'o': 15, 'p': 16, \n",
    "        'q': 17, 'r': 18, 's': 19, 't': 20, 'u': 21, 'v': 22, 'w': 23, 'x': 24, 'y': 25, 'z': 26}\n",
    "        hs, n, p = 0, len(s), pow(power, k-1)\n",
    "\n",
    "        for i in range(k-1,-1,-1):\n",
    "            hs = hs * power + d[s[i]]\n",
    "    \n",
    "        for i in range(n-k+1):\n",
    "            if hs % modulo == hashValue:\n",
    "                return s[i:i+k]\n",
    "                \n",
    "            if i<n-k: \n",
    "                hs -= d[s[i]]\n",
    "                hs = hs//power + d[s[i+k]]*p"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subStrHash(self, s: str, power: int, modulo: int, k: int, hashValue: int) -> str:\n",
    "        d = {'a': 1, 'b': 2, 'c': 3, 'd': 4, 'e': 5, 'f': 6, 'g': 7, 'h': 8, 'i': 9, 'j': 10, 'k': 11, \n",
    "        'l': 12, 'm': 13, 'n': 14, 'o': 15, 'p': 16, 'q': 17, 'r': 18, 's': 19, 't': 20, 'u': 21, 'v': 22,\n",
    "        'w': 23, 'x': 24, 'y': 25, 'z': 26}\n",
    "\n",
    "        hs, n, s, p = 0, len(s), s[::-1], pow(power, k-1)\n",
    "\n",
    "        for i in range(k):\n",
    "            hs = hs * power + d[s[i]]\n",
    "    \n",
    "        for i in range(n - k + 1):\n",
    "            if hs % modulo == hashValue:\n",
    "                s0 = s[i:i+k]\n",
    "                \n",
    "            if i < n - k: \n",
    "                hs -= p * d[s[i]] \n",
    "                hs = hs * power + d[s[i+k]]\n",
    "        return s0[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def subStrHash(self, s, power, modulo, k, hashValue):\n",
    "        h, h1, lst = 0, power ** (k - 1), list(map(lambda c : ord(c) - 96, s))\n",
    "        for i in range(k - 1, -1, -1): \n",
    "            h = lst[i] + h * power\n",
    "        if h % modulo == hashValue:     \n",
    "            return s[:k]\n",
    "        for i in range(1, len(s) - k + 1):\n",
    "            h = (h - lst[i - 1]) // power + lst[i + k - 1] * h1\n",
    "            if h % modulo == hashValue: \n",
    "                return s[i : i + k]        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subStrHash(self, s: str, power: int, modulo: int, k: int, hashValue: int) -> str:\n",
    "        p, m, n = power, modulo, len(s)\n",
    "        f = [0] * (n + 1)\n",
    "        t = 0 # 123 -> 321\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            t = (t * p + ord(s[i]) - ord('a') + 1) % m\n",
    "            f[i] = t\n",
    "        #[n-k, n-1]\n",
    "        ans = \"\"\n",
    "        for i in range(n - k, -1, -1):\n",
    "            if (f[i] - f[i+k] * pow(p, k, m) + m) % m == hashValue:\n",
    "                ans = s[i:i+k]\n",
    "        return ans\n",
    "                \n",
    "            \n",
    "            \n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subStrHash(self, s: str, power: int, modulo: int, k: int, hashValue: int) -> str:\n",
    "        n = len(s)\n",
    "        val = {chr(i + 97): i + 1 for i in range(26)}\n",
    "        powers = [pow(power, x, modulo) for x in range(k + 1)]\n",
    "        curHashVal = sum(powers[i - n + k] * val[s[i]] % modulo for i in range(n - k, n)) % modulo\n",
    "        ansI = n if curHashVal == hashValue else 0\n",
    "        for i in range(n - 1, k - 1, -1):\n",
    "            curHashVal = (curHashVal * power - val[s[i]] * powers[k] + val[s[i - k]]) % modulo\n",
    "            if curHashVal == hashValue:\n",
    "                ansI = i\n",
    "        return s[ansI - k: ansI]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subStrHash(self, s: str, power: int, modulo: int, k: int, hashValue: int) -> str:\n",
    "        n = len(s)\n",
    "        val = {chr(i + 97): i + 1 for i in range(26)}\n",
    "        powers = [pow(power, x, modulo) for x in range(k + 1)]\n",
    "        curHashVal = sum(powers[i - n + k] * val[s[i]] % modulo for i in range(n - k, n)) % modulo\n",
    "        ansI = n if curHashVal == hashValue else 0\n",
    "        for i in range(n - 1, k - 1, -1):\n",
    "            curHashVal = (curHashVal * power % modulo - val[s[i]] * powers[k] % modulo + val[s[i - k]]) % modulo\n",
    "            if curHashVal == hashValue:\n",
    "                ansI = i\n",
    "        return s[ansI - k: ansI]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "class Solution:\n",
    "    def subStrHash(self, s: str, power: int, modulo: int, k: int, hashValue: int) -> str:\n",
    "        n = len(s)\n",
    "        pt = 1\n",
    "        p = [1]*k\n",
    "        for i in range(1, k):\n",
    "            pt = (pt*power)%modulo\n",
    "            p[i] = pt\n",
    "        v = [ord(i) - 96 for i in s]\n",
    "        curHash = 0\n",
    "        for i in range(k):\n",
    "            curHash = (curHash + (p[i]*v[n-k+i])%modulo)%modulo\n",
    "        pos = -1\n",
    "        if curHash == hashValue:\n",
    "            pos = n-k               \n",
    "        for i in range(n-k-1, -1, -1):\n",
    "            curHash = ((curHash - (p[-1]*v[i+k])%modulo)*power + v[i]%modulo)%modulo\n",
    "            if curHash == hashValue:\n",
    "                pos = i\n",
    "        return s[pos:pos+k]\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subStrHash(self, s: str, power: int, modulo: int, k: int, hashValue: int) -> str:\n",
    "        n, r, q, m, x = len(s), -1, deque([0], maxlen=k), pow(power, k, modulo), 0\n",
    "        for i, c in enumerate(reversed(s), 1):\n",
    "            x = (q[-1] * power + ord(c) - 96) % modulo\n",
    "            if i >= k and (x - m * q[0]) % modulo == hashValue:\n",
    "                r = n-i\n",
    "            q.append(x)\n",
    "        return s[r:r+k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subStrHash(self, s: str, power: int, modulo: int, k: int, hashValue: int) -> str:\n",
    "        n = len(s)\n",
    "        val = {chr(i + 97): i + 1 for i in range(26)}\n",
    "        powers = [pow(power, x, modulo) for x in range(k + 1)]\n",
    "        curHashVal = sum(powers[i - n + k] * val[s[i]] % modulo for i in range(n - k, n)) % modulo\n",
    "        ansI = n if curHashVal == hashValue else 0\n",
    "        for i in range(n - 1, k - 1, -1):\n",
    "            curHashVal = (curHashVal * power - val[s[i]] * powers[k] + val[s[i - k]]) % modulo\n",
    "            if curHashVal == hashValue:\n",
    "                ansI = i\n",
    "                print(ansI)\n",
    "        return s[ansI - k: ansI]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subStrHash(self, s: str, power: int, modulo: int, k: int, hashValue: int) -> str:\n",
    "        n = len(s)\n",
    "        val = {chr(i + 97): i + 1 for i in range(26)}\n",
    "        powers = [pow(power, x, modulo) for x in range(k + 1)]\n",
    "        curHashVal = sum(powers[i - n + k] * val[s[i]] % modulo for i in range(n - k, n)) % modulo\n",
    "        ansI = n if curHashVal == hashValue else 0\n",
    "        for i in range(n - 1, k - 1, -1):\n",
    "            curHashVal = (curHashVal * power - val[s[i]] * powers[k] + val[s[i - k]]) % modulo\n",
    "            if curHashVal == hashValue:\n",
    "                ansI = i\n",
    "        return s[ansI - k: ansI]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subStrHash(self, s: str, power: int, modulo: int, k: int, hashValue: int) -> str:\n",
    "        n = len(s)\n",
    "        # l = r = 0\n",
    "        # def getnum(ch):\n",
    "        #     ans = ord(ch) - ord('a') + 1\n",
    "        #     return ans\n",
    "        # t = getnum(s[0])\n",
    "        # while r < n:\n",
    "        d = [1]\n",
    "        for i in range(k-1):\n",
    "            t = (d[-1] * power) % modulo\n",
    "            d.append(t)\n",
    "        hash = {}\n",
    "        for i in range(26):\n",
    "            ch = chr(ord('a') + i)\n",
    "            hash[ch] = i + 1\n",
    "        t = 0\n",
    "        for i in range(n-k, n):\n",
    "            t = (t + hash[s[i]] * d[i-n+k]) % modulo\n",
    "        if t == hashValue:\n",
    "            ans = n-k\n",
    "        for l in range(n-k-1, -1, -1):\n",
    "            t = ((t - hash[s[l+k]] * d[k-1]) * power + hash[s[l]]) % modulo\n",
    "            if t == hashValue:\n",
    "                ans = l\n",
    "        return s[ans:ans + k]\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subStrHash(self, s: str, power: int, modulo: int, k: int, hashValue: int) -> str:\n",
    "        n=len(s);power%=modulo\n",
    "        mp={chr(96+i):i for i in range(1,27)}\n",
    "        f,g,h=[0]*(k+1),[0]*(k+1),[1]*(k+1)\n",
    "        for i in range(1,k+1):h[i]=h[i-1]*power%modulo\n",
    "        for i in range(0,n,k):\n",
    "            for j in range(k-1,-1,-1):f[j]=(f[j+1]*power+mp[s[i+j]])%modulo\n",
    "            if(f[0]==hashValue):return s[i:i+k]\n",
    "            for j in range(1,min(k,n-i-k+1)):g[j]=(g[j-1]+mp[s[i+k+j-1]]*h[j-1])%modulo\n",
    "            for j in range(1,min(k,n-i-k+1)):\n",
    "                if((f[j]+g[j]*h[k-j])%modulo==hashValue):return s[(i+j):(i+j+k)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subStrHash(self, s: str, power: int, modulo: int, k: int, hashValue: int) -> str:\n",
    "\n",
    "        n = len(s)\n",
    "        h = [0] * (n+1)\n",
    "        p = [1] * (n+1)\n",
    "        for i in range(n-1, -1, -1):\n",
    "            h[i] = (h[i+1] * power + ord(s[i]) - ord('a') + 1) % modulo\n",
    "            p[n-i] = (p[n-i-1] * power) % modulo\n",
    "        def calc(l,r):\n",
    "            return (h[l] - (h[r] * p[r - l]) % modulo + modulo) % modulo\n",
    "      \n",
    "        for i in range(n-k+1):\n",
    "            tmp = calc(i, i+k)\n",
    "        \n",
    "            if tmp == hashValue:\n",
    "                return s[i:i+k]\n",
    "        return ''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 滚动哈希，e.g.：1044. 最长重复子串, 单进制\n",
    "# 高位 -> 低位\n",
    "class RollingHash:\n",
    "    def __init__(self, s, MOD=10**9+7, base=71):\n",
    "        n = len(s)  # s 要处理的字符串\n",
    "        self.MOD = MOD # 是必要的，否则计算速度超级慢\n",
    "        # encoder：获取字母在字母表中的顺序:\n",
    "        ecd = {chr(i + ord('a')): i + 1 for i in range(26)}\n",
    "        self.hvs, self.pow = [0] * (n + 1), [1] * (n + 1)\n",
    "        for i in range(n):\n",
    "            self.hvs[i + 1] = (self.hvs[i] * base + ecd[s[i]]) % self.MOD\n",
    "            self.pow[i + 1] = (self.pow[i] * base) % self.MOD\n",
    "\n",
    "    # 获取子串s[start:end)哈希值，元组形式返回:\n",
    "    def get_hash(self, start, end):\n",
    "        return (self.hvs[end] - self.hvs[start] * self.pow[end - start]) % self.MOD\n",
    "\n",
    "class Solution:\n",
    "    def subStrHash(self, s: str, power: int, modulo: int, k: int, hashValue: int) -> str:\n",
    "        rh = RollingHash(s[::-1], MOD=modulo, base=power)\n",
    "        left, right = 0, 0\n",
    "        n = len(s)\n",
    "        for l, r in zip(range(n+1), range(k, n+1)):\n",
    "            if rh.get_hash(l, r) == hashValue:\n",
    "                left, right = l, r\n",
    "        return s[n-right:n-left]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subStrHash(self, s: str, power: int, modulo: int, k: int, hashValue: int) -> str:\n",
    "\n",
    "        L=k\n",
    "        text=s[::-1]\n",
    "        n = len(text)\n",
    "        pre = [0] * (n + 1)\n",
    "        mul = [1] + [0] * n\n",
    "        mod = modulo\n",
    "        base = power\n",
    "\n",
    "        for i in range(1, n + 1):\n",
    "            pre[i] = (pre[i - 1] * base + ord(text[i - 1])-ord('a')+1) % mod\n",
    "            mul[i] = mul[i - 1] * base % mod  # 预先计算幂\n",
    "\n",
    "        def get_hash(l, r):  # 对于数组内任意一个区间[l,r] 得到该区间内的hash代表\n",
    "            return (pre[r + 1] - pre[l] * mul[r - l + 1] + mod) % mod\n",
    "\n",
    "        answer=\"\"\n",
    "        h = get_hash(0, L - 1)\n",
    "        if h == hashValue:  # 判断该子串在以前出现过\n",
    "            answer = s[n-n-L:n]\n",
    "\n",
    "        aL = mul[L]  # 计算base的L次幂\n",
    "        for start in range(1, len(text) - L + 1):\n",
    "            # compute rolling hash in O(1) time\n",
    "            h = (h * base - (ord(text[start - 1])-ord('a')+1) * aL + ord(text[start + L - 1])-ord('a')+1) % mod\n",
    "            if h==hashValue:\n",
    "                answer=s[n-n-L-start:n-start]\n",
    "\n",
    "        return answer\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
